package code.daily;

import utils.ListNode;
import utils.TreeNode;

import java.util.*;

/**
 * @author 26029
 * @date 2025/5/12
 * @description
 */
public class TOP75 {
    // 1448. 统计二叉树中好节点的数目
    int ans1448;

    public int goodNodes(TreeNode root) {
        ans1448 = 0;
        DFS1448(root, Integer.MIN_VALUE);
        return ans1448;
    }

    private void DFS1448(TreeNode root, int maxPre) {
        if (root == null)
            return;
        // 如果 root 符合，ans++
        if (root.val >= maxPre)
            ans1448++;
        maxPre = Math.max(root.val, maxPre);
        DFS1448(root.left, maxPre);
        DFS1448(root.right, maxPre);
    }

    // 1372. 二叉树中的最长交错路径
    int ans1372;

    public int longestZigZag(TreeNode root) {
        ans1372 = 0;
        DFS1372(root);
        return Math.max(0, ans1372 - 1);
    }

    private int[] DFS1372(TreeNode root) {
        // 函数返回它向左&向右子树的最长交错路径包含的节点数
        if (root == null)
            return new int[]{0, 0};
        int[] leftMax = DFS1372(root.left);
        int[] rightMax = DFS1372(root.right);
        // 答案更新
        int rootAndLeft = leftMax[1] + 1;
        int rootAndRight = rightMax[0] + 1;
        ans1372 = Math.max(ans1372, Math.max(rootAndLeft, rootAndRight));
        // 返回
        return new int[]{rootAndLeft, rootAndRight};
    }

    // 1161. 最大层内元素和
    public int maxLevelSum(TreeNode root) {
        // 树中的节点数在 [1, 10^4]范围内
        int maxSum = Integer.MIN_VALUE;
        int maxLevel = 0;
        int nowLevel = 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            nowLevel++;
            int nowLevelSize = queue.size();
            int nowLevelSum = 0;
            for (int i = 0; i < nowLevelSize; i++) {
                TreeNode node = queue.poll();
                nowLevelSum += node.val;
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            if (nowLevelSum > maxSum) {
                maxSum = nowLevelSum;
                maxLevel = nowLevel;
            }
        }
        return maxLevel;
    }

    // 1679. K 和数对的最大数目
    public int maxOperations(int[] nums, int k) {
        // 1. 排序后双指针 O(nlogn) 2. map O(n)
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int num : nums) {
            int mapValue = map.getOrDefault(k - num, 0);
            if (mapValue > 0) {
                ans++;
                if (mapValue == 1) map.remove(k - num);
                else map.put(k - num, mapValue - 1);
            } else {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
        }
        return ans;
    }

    // 334. 递增的三元子序列
    public boolean increasingTriplet(int[] nums) {
        // O(n) O(n) 解法
        int len = nums.length;
        // nums =   2 1 5 0 4 6
        // pre  = max 2 1 1 0 0
        // aft  =   6 6 6 6 6 min
        int[] preMin = new int[len];
        int[] aftMax = new int[len];
        preMin[0] = Integer.MAX_VALUE;
        aftMax[len - 1] = Integer.MIN_VALUE;
        for (int i = 1; i < len; i++)
            preMin[i] = Math.min(preMin[i - 1], nums[i - 1]);
        for (int i = len - 2; i >= 0; i--)
            aftMax[i] = Math.max(aftMax[i + 1], nums[i + 1]);
        for (int i = 0; i < len; i++) {
            if (preMin[i] < nums[i] && nums[i] < aftMax[i])
                return true;
        }
        return false;
    }

    public boolean increasingTriplet_ono1(int[] nums) {
        // O(n) O(1) 解法
        int len = nums.length;
        int first = nums[0];
        int second = Integer.MAX_VALUE;
        for (int i = 1; i < len; i++) {
            if (nums[i] > second)
                return true;
            else if (nums[i] > first)
                second = nums[i];
            else
                first = nums[i];
        }
        return false;
    }

    // 1456. 定长子串中元音的最大数目
    public int maxVowels(String s, int k) {
        // 1 <= s.length <= 10^5  1 <= k <= s.length
        int len = s.length();
        int max = 0, now = 0;
        for (int i = 0; i < k; i++) {
            if (isAEIOU(s.charAt(i))) {
                now++;
                if (now > max) max = now;
            }
        }
        for (int i = k; i < len; i++) {
            // right=i left=i-k+1 last=i-k
            if (isAEIOU(s.charAt(i - k)))
                now--;
            if (isAEIOU(s.charAt(i))) {
                now++;
                if (now > max) max = now;
            }
        }
        return max;
    }

    private boolean isAEIOU(char c) {
        switch (c) {
            case 'a', 'e', 'i', 'o', 'u' -> {
                return true;
            }
        }
        return false;
    }

    // 1004. 最大连续1的个数 III
    public int longestOnes(int[] nums, int k) {
        // 保证滑动窗口中0的个数不超过k
        int len = nums.length;
        int max = 0, now = 0;
        int zero_num = 0;
        int left = 0, right = 0;
        while (right < len) {
            if (nums[right] == 0) {
                zero_num++;
                while (zero_num > k) {
                    if (nums[left] == 0) zero_num--;
                    else now--;
                    left++;
                }
            } else {
                now++;
            }
            max = Math.max(max, now + zero_num);
            right++;
        }
        return max;
    }

    // 1493. 删掉一个元素以后全为 1 的最长子数组
    public int longestSubarray(int[] nums) {
        // 1 <= nums.length <= 105
        int len = nums.length;
        int zero_num = 0, zero_pos = -1;
        int one_num = 0, max = 0;
        int left = 0, right = 0;
        while (right < len) {
            if (nums[right] == 0) {
                if (zero_num == 0) {
                    zero_num = 1;
                } else {
                    one_num -= (zero_pos - left);
                    left = zero_pos + 1;
                }
                zero_pos = right;
            } else {
                one_num++;
            }
            max = Math.max(max, one_num);
            right++;
        }
        // 如果没有0，那么强行删一个
        if (zero_num == 0)
            max--;
        return max;
    }

    // 1657. 确定两个字符串是否接近
    public boolean closeStrings(String word1, String word2) {
        // 1 <= word1.length, word2.length <= 105
        int len = word1.length(), len2 = word2.length();
        // 判断条件：1. 长度相等 2. 字符集是否一致 3. 字符集频率相等
        // 长度是否相等
        if (len != len2) return false;
        // 字符集是否一致
        int[] map1 = new int[26], map2 = new int[26];
        for (int i = 0; i < len; i++) {
            char c1 = word1.charAt(i), c2 = word2.charAt(i);
            map1[c1 - 'a']++;
            map2[c2 - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (map1[i] != 0 && map2[i] == 0 || map1[i] == 0 && map2[i] != 0)
                return false;
        }
        // 字符集频率是否相等
        Arrays.sort(map1);
        Arrays.sort(map2);
        for (int i = 0; i < 26; i++) {
            if (map1[i] != map2[i])
                return false;
        }
        return true;
    }

    // 2352. 相等行列对
    public int equalPairs(int[][] grid) {
        int n = grid.length;
        int ans = 0;
        Map<List<Integer>, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < n; j++)
                list.add(grid[i][j]);
            map.put(list, map.getOrDefault(list, 0) + 1);
        }
        for (int j = 0; j < n; j++) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++)
                list.add(grid[i][j]);
            if (map.containsKey(list))
                ans += map.get(list);
        }
        return ans;
    }

    // 735. 小行星碰撞
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new LinkedList<>();
        for (int num : asteroids) {
            if (num > 0)
                stack.push(num);
            else { // num < 0
                // 这个负数有没有爆 没有爆就放到stack中
                boolean isExplosion = false;
                while (!stack.isEmpty() && stack.peek() > 0) {
                    if (num + stack.peek() < 0) {
                        stack.pop();
                        continue;
                    }
                    isExplosion = true;
                    if (num + stack.peek() == 0) {
                        stack.pop();
                    }
                    break;
                }
                if (!isExplosion)
                    stack.push(num);
            }
        }
        int ansLen = stack.size();
        int[] ans = new int[ansLen];
        for (int i = ansLen - 1; i >= 0; i--) {
            ans[i] = stack.pop();
        }
        return ans;
    }

    // 649. Dota2 参议院
    public String predictPartyVictory(String senate) {
        char[] chars = senate.toCharArray();
        int len = chars.length;
        boolean[] dead = new boolean[len];
        int penaltyTOR = 0, penaltyTOD = 0;
        int aliveR = 0, aliveD = 0;
        for (char c : chars) {
            if (c == 'R') aliveR++;
            else aliveD++;
        }
        while (aliveR > 0 && aliveD > 0) {
            for (int i = 0; i < len; i++) {
                if (dead[i]) continue;
                if (chars[i] == 'R') {
                    if (penaltyTOR > 0) {
                        dead[i] = true;
                        penaltyTOR--;
                        aliveR--;
                    } else {
                        penaltyTOD++;
                    }
                } else {
                    if (penaltyTOD > 0) {
                        dead[i] = true;
                        penaltyTOD--;
                        aliveD--;
                    } else {
                        penaltyTOR++;
                    }
                }
            }
        }
        if (aliveD == 0) return "Radiant";
        else return "Dire";
    }

    // 2095. 删除链表的中间节点
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null)
            return null;
        // get mid node
        ListNode pre = null, node = head, fast = head.next;
        while (fast != null && fast.next != null) {
            pre = node;
            node = node.next;
            fast = fast.next.next;
        }
        // 奇数个，此时fast==null，pre的下一个是要删除的
        if (fast == null) {
            pre.next = node.next;
        } else { // 偶数个，此时fast.next==null，node的下一个是要删除的
            node.next = node.next.next;
        }
        return head;
    }

    // 328. 奇偶链表
    public ListNode oddEvenList(ListNode head) {
        // 0 <= n <= 10^4
        if (head == null || head.next == null)
            return head;
        ListNode node = head.next.next;
        ListNode pre = head.next;
        ListNode lastOdd = head;
        boolean isOdd = true;
        while (node != null) {
            ListNode next = node.next;
            // 如果是奇数下标，把他移到前面去，最后pre不变，node变为开始的node.next
            if (isOdd) {
                pre.next = next;
                ListNode lastOddNext = lastOdd.next;
                lastOdd.next = node;
                node.next = lastOddNext;
                lastOdd = node;
            } else { // 偶数下标，pre变为node，node变为node.next
                pre = node;
            }
            isOdd = !isOdd;
            node = next;
        }
        return head;
    }

    // 2130. 链表最大孪生和
    public int pairSum(ListNode head) {
        // 链表的节点数目是 [2, 10^5] 中的 偶数  1 <= Node.val <= 10^5
        // O(n) + O(1) 先翻转后半部分链表，再同时俩指针顺序查找
        if (head == null || head.next == null)
            return -1;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow之后需要翻转
        ListNode right = slow.next, left = null;
        while (right != null) {
            ListNode rightNext = right.next;
            right.next = left;
            left = right;
            right = rightNext;
        }
        slow.next = left;
        // 双指针找最大值
        ListNode n1 = head, n2 = slow.next;
        int ans = 0;
        while (n1 != null && n2 != null) {
            ans = Math.max(ans, n1.val + n2.val);
            n1 = n1.next;
            n2 = n2.next;
        }
        return ans;
    }

    // 841. 钥匙和房间
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        // 2 <= roomNum <= 1000
        int roomNum = rooms.size();
        boolean[] isVisited = new boolean[roomNum];
        isVisited[0] = true;
        int visitedNum = 1; // 房间0默认能访问
        Deque<Integer> keys = new LinkedList<>();
        for (int k : rooms.get(0))
            keys.offer(k);
        while (!keys.isEmpty()) {
            int key = keys.poll();
            if (!isVisited[key]) {
                isVisited[key] = true;
                visitedNum++;
                for (int k : rooms.get(key))
                    keys.offer(k);
            }
        }
        return visitedNum == roomNum;
    }

    // 547. 省份数量
    public int findCircleNum(int[][] isConnected) {
        // 无向图 isConnected[i][j] == isConnected[j][i]
        int city = isConnected.length;
        int province = 0;
        boolean[] visited = new boolean[city];
        for (int i = 0; i < city; i++) {
            if (!visited[i]) {
                province++;
                findAllCity(i, isConnected, visited);
            }
        }
        return province;
    }

    private void findAllCity(int city, int[][] isConnected, boolean[] visited) {
        int len = isConnected.length;
        visited[city] = true;
        for (int i = 0; i < len; i++) {
            if (!visited[i] && isConnected[city][i] == 1)
                findAllCity(i, isConnected, visited);
        }
    }

    // 1466. 重新规划路线
    public int minReorder(int n, int[][] connections) {
        List<Integer>[] nodeTo = new List[n];
        List<Integer>[] toNode = new List[n];
        for (int i = 0; i < n; i++) {
            nodeTo[i] = new ArrayList<>(2);
            toNode[i] = new ArrayList<>(2);
        }
        for (int[] connection : connections) {
            nodeTo[connection[0]].add(connection[1]);
            toNode[connection[1]].add(connection[0]);
        }
        boolean[] visited = new boolean[n];
        int change = 0;
        Deque<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            visited[node] = true;
            // 如果有没有visit过并且node指向他的节点，更换方向
            if (!nodeTo[node].isEmpty()) {
                for (int nextNode : nodeTo[node]) {
                    if (visited[nextNode])
                        continue;
                    change++;
                    queue.offer(nextNode);
                }
            }
            // 如果有没有visited过并且指向node的节点，正常
            if (!toNode[node].isEmpty()) {
                for (int nextNode : toNode[node]) {
                    if (visited[nextNode])
                        continue;
                    queue.offer(nextNode);
                }
            }
        }
        return change;
    }

    // 1926. 迷宫中离入口最近的出口
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> queue = new LinkedList<>();
        // 注意 要在加入队列的时候设置已访问，避免其他路线也访问到这个地方
        queue.offer(entrance);
        visited[entrance[0]][entrance[1]] = true;
        int step = -1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            for (int i = 0; i < size; i++) {
                int[] nowPos = queue.poll();
                int x = nowPos[0], y = nowPos[1];
                // 如果到达终点，结束
                if (!(x == entrance[0] && y == entrance[1]) && (x == 0 || x == m - 1 || y == 0 || y == n - 1))
                    return step;
                // 遍历他的四周看看
                for (int[] d : dir) {
                    int newX = x + d[0], newY = y + d[1];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n)
                        continue;
                    if (visited[newX][newY] || maze[newX][newY] == '+')
                        continue;
                    queue.offer(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }
        return -1;
    }

    // 2336. 无限集中的最小数字
    class SmallestInfiniteSet {
        PriorityQueue<Integer> priorityQueue;
        int number;

        public SmallestInfiniteSet() {
            // 如果有添加回去的数，代表优先队列不空，先从优先队列里拿，否则直接拿number
            priorityQueue = new PriorityQueue<>(); // 添加回无限集的比number小的数
            number = 1; // 无限集当前最小的正整数
        }

        public int popSmallest() {
            // 返回存在于无限集的最小正整数，并移除
            if (priorityQueue.isEmpty()) {
                number++;
                return number - 1;
            }
            return priorityQueue.poll();
        }

        public void addBack(int num) {
            // 如果元素在无限集中不存在，添加到无限集
            // logic: 如果addBack一个大于等于当前无限集的最小值的数 或 加了一个队列中已经有的数 相当于没加
            if (number > num && !priorityQueue.contains(num))
                priorityQueue.offer(num);
        }
    }

    // TODO 有点难 搁置 2542. 最大子序列的分数
    public long maxScore(int[] nums1, int[] nums2, int k) {
        // 1 <= k <= n   0 <= nums1[i], nums2[j] <= 10^5
        int n = nums1.length;
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = nums1[i];
            nums[i][1] = nums2[i];
        }
        Arrays.sort(nums, (o1, o2) -> Integer.compare(o2[1], o1[1]));
        // nums1 =  3  1 3 1 2
        // nums2 =  10 9 7 6 5
        int max = 0;
        return 0L;
    }

    // 2462. 雇佣 K 位工人的总代价
    public long totalCost(int[] costs, int k, int candidates) {
        int len = costs.length;
        PriorityQueue<Integer> left = new PriorityQueue<>(), right = new PriorityQueue<>();
        int leftPointer = 0, rightPointer = len - 1;
        // [57,33,26,76,14,67,24,90,72,37,30] k=11 candidates =2
        //   x  x  l                 r  y  y
        while (leftPointer < candidates && leftPointer <= rightPointer) {
            left.offer(costs[leftPointer]);
            leftPointer++;
        }
        while (len - rightPointer - 1 < candidates && rightPointer >= leftPointer) {
            right.offer(costs[rightPointer]);
            rightPointer--;
        }
        long all = 0;
        while (k > 0) {
            // 如果right为空，说明数字全在左面
            if (right.isEmpty()) {
                all += left.poll();
                k--;
                continue;
            }
            // 如果left为空，说明数字全在右面
            if (left.isEmpty()) {
                all += right.poll();
                k--;
                continue;
            }
            // left right 都有
            int leftMin = left.peek(), rightMin = right.peek();
            if (leftMin <= rightMin) {
                all += left.poll();
                if (leftPointer <= rightPointer) {
                    left.offer(costs[leftPointer]);
                    leftPointer++;
                }
            } else {
                all += right.poll();
                if (leftPointer <= rightPointer) {
                    right.offer(costs[rightPointer]);
                    rightPointer--;
                }
            }
            k--;
        }
        return all;
    }

    // 790. 多米诺和托米诺平铺
    public int numTilings(int n) {
        if (n == 1)
            return 1;
        int mod = 1000000007;
        long[] dp = new long[n + 1];
        dp[1] = dp[0] = 1;
        dp[2] = 2;
        // 基于下面的初始递推写法优化
        // dp[n] = dp[n-1] + dp[n-2] + 2 * (dp[n-3] + dp[n-4] + ... + dp[1] + dp[0];
        // dp[n-1] = dp[n-2] + dp[n-3] + 2 * (dp[n-4] + dp[n-5] + ... + dp[1] + dp[0]);
        // dp[n] = dp[n-1] + dp[n-1] + dp[n-3] = dp[n-1] * 2 + dp[n-3];
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % mod;
        }
        return (int) dp[n];
    }

    public int numTilings_primary(int n) {
        // 不考虑模的情况下，时间复杂度较为高的二重循环递推
        // 可以优化为上面的写法↑
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 1; // dp[2] = 2 // dp[3] = 5
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            for (int j = 3; i - j >= 0; j++) {
                dp[i] += 2 * dp[i - j];
            }
        }
        return (int) dp[n];
    }

    // 901. 股票价格跨度
    class StockSpanner {
        // 单调栈（递减，可以找他之前第一个比他大的）
        Deque<Integer> stack;
        List<Integer> list;

        public StockSpanner() {
            stack = new LinkedList<>();
            list = new ArrayList<>();
        }

        public int next(int price) {
            list.add(price);
            int len = list.size();
            int pos;
            while (!stack.isEmpty() && list.get(stack.peek()) <= price) {
                stack.pop();
            }
            if (!stack.isEmpty())
                pos = stack.peek(); // 找到数组左面第一个比他大的位置
            else
                pos = -1;

            stack.push(len - 1);
            return len - 1 - pos;
        }
    }


    // 1268. 搜索推荐系统
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> lists = new ArrayList<>();
        DTreeNode dict = new DTreeNode();
        // 把products加入字典
        for (String product : products) {
            char[] chars = product.toCharArray();
            DTreeNode node = dict;
            for (char c : chars) {
                int pos = c - 'a';
                if (node.children[pos] == null)
                    node.children[pos] = new DTreeNode();
                node = node.children[pos];
            }
            node.isWord = true;
            node.word = product;
        }
        // 查询searchWord
        char[] searchChars = searchWord.toCharArray();
        DTreeNode baseNode = dict; // 每次从baseNode往后找最多三个
        for (char searchChar : searchChars) {
            List<String> list = new ArrayList<>();
            int pos = searchChar - 'a';
            baseNode = baseNode == null ? null : baseNode.children[pos];
            // 从这里接着往后找最多三个
            DFS_DTree(baseNode, list);
            // 加到lists中
            lists.add(list);
        }

        return lists;
    }

    private void DFS_DTree(DTreeNode node, List<String> list) {
        if (node == null || list.size() == 3)
            return;
        if (node.isWord) {
            list.add(node.word);
            // 剪枝，如果出来了list.size()==3，就不用往后了
            if (list.size() == 3)
                return;
        }
        for (int i = 0; i < 26; i++) {
            DFS_DTree(node.children[i], list);
        }
    }

    class DTreeNode {
        DTreeNode[] children;
        boolean isWord;
        String word;

        public DTreeNode() {
            isWord = false;
            children = new DTreeNode[26];
        }
    }

    // 1318. 或运算的最小翻转次数
    public int minFlips(int a, int b, int c) {
        // 1 <= a,b,c <= 10^9
        int change = 0;
        for (int i = 1; i <= 31; i++) {
            int aa = a & 1, bb = b & 1, cc = c & 1;
            if ((aa | bb) != cc) {
                if (cc == 1)
                    change++;
                else {
                    if (aa == 1)
                        change++;
                    if (bb == 1)
                        change++;
                }
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return change;
    }

    // 875. 爱吃香蕉的珂珂
    public int minEatingSpeed(int[] piles, int h) {
        int max = Arrays.stream(piles).max().getAsInt();
        int min = 1;
        int min_speed = Integer.MAX_VALUE;
        while (min <= max) {
            int mid = min + (max - min) / 2;
            if (canEatAll(piles, h, mid)) {
                min_speed = mid;
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        return min_speed;
    }

    private boolean canEatAll(int[] piles, int h, int k) {
        long hours = 0L;
        for (int pile : piles) {
            int chu = pile / k;
            int yu = pile % k;
            hours += chu;
            if (yu > 0) hours++;
        }
        return hours <= h;
    }

    // 162. 寻找峰值
    public int findPeakElement(int[] nums) {
        // nums[-1] = nums[n] = -∞ 一直往高处走
        // -2^31 <= nums[i] <= 2^31 - 1
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 如果是峰值，返回结果
            if (compare162(nums, mid, mid + 1) > 0 && compare162(nums, mid, mid - 1) > 0)
                return mid;
            // 如果nums[mid] < nums[mid + 1]范围设置为[mid + 1, right]
            if (compare162(nums, mid, mid + 1) < 0)
                left = mid + 1;
            // 如果nums[mid] > nums[mid + 1]范围设置为[left, mid]
            else
                right = mid;
        }
        return -1;
    }

    // 2300. 咒语和药水的成功对数
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int len1 = spells.length, len2 = potions.length;
        int[] ans = new int[len1];
        Arrays.sort(potions);
        for (int i = 0; i < len1; i++) {
            int spell = spells[i];
            int left = 0, right = len2 - 1;
            int smallestPos = len2;
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if ((long) spell * potions[mid] >= success) {
                    right = mid - 1;
                    smallestPos = mid;
                } else {
                    left = mid + 1;
                }
            }
            ans[i] = len2 - smallestPos;
        }
        return ans;
    }

    private int compare162(int[] nums, int x, int y) {
        long numX = (x >= nums.length || x < 0) ? Long.MIN_VALUE : nums[x];
        long numY = (y >= nums.length || y < 0) ? Long.MIN_VALUE : nums[y];
        return Long.compare(numX, numY);
    }

    // 2390. 从字符串中移除星号
    public String removeStars(String s) {
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (c == '*' && sb.length() > 0) {
                sb.deleteCharAt(sb.length() - 1);
                continue;
            }
            sb.append(c);
        }
        return sb.toString();
    }

    // 2542. 最大子序列的分数
    public long maxScore_2542(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int[][] lists = new int[n][2];
        for (int i = 0; i < n; i++) {
            lists[i][0] = nums1[i];
            lists[i][1] = nums2[i];
        }
        // 按照 nums2 降序排序
        Arrays.sort(lists, ((o1, o2) -> {return Integer.compare(o2[1], o1[1]);}));

        // nums1 14   2  1  12
        // nums2 13  11  7   6
        // 优先队列
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        long sum = 0L;
        long ans = 0L;
        for (int i = 0; i < k - 1; i++) {
            sum += lists[i][0];
            priorityQueue.offer(lists[i][0]);
        }
        for (int i = k - 1; i < n; i++) {
            sum += lists[i][0];
            priorityQueue.offer(lists[i][0]);
            ans = Math.max(ans, sum * lists[i][1]);
            sum -= priorityQueue.poll();
        }

        return ans;
    }

    public static void main(String[] args) {
        TOP75 top75 = new TOP75();
        int[] piles = new int[]{805306368, 805306368, 805306368};
        System.out.println(top75.minEatingSpeed(piles, 1000000000));
    }
}
